package demo8;

public class Solution {
    //1.剑指 Offer II 045. 二叉树最底层最左边的值(dfs)
    private int leftPath = -1;//记录左子树的深度
    private int ret = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return ret;
    }
    private void dfs(TreeNode root, int path) {
        if(root == null) {
            return;
        }
        dfs(root.left, path + 1);
        dfs(root.right, path + 1);
        if(root.left == null && root.right == null && path > leftPath) {
            ret = root.val;
            leftPath = path;
        }
    }
    //1.剑指 Offer II 045. 二叉树最底层最左边的值(dfs优化)
    private int leftPath;
    private int ret;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return ret;
    }
    private void dfs(TreeNode root, int path) {
        if(root == null) {
            return;
        }
        path++;
        dfs(root.left, path);
        dfs(root.right, path);
        if(path > leftPath) {
            ret = root.val;
            leftPath = path;
        }
    }
    //2.剑指 Offer II 047. 二叉树剪枝(dfs)
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        return root;
    }
    //3.剑指 Offer II 049. 从根节点到叶节点的路径数字之和(dfs)
    private int ret;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ret;
    }
    private void dfs(TreeNode root, int sum) {
        if(root == null) {
            return;
        }
        sum = root.val + sum * 10;
        if(root.left == null && root.right == null) {
            ret += sum;
            return;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }
    //4.剑指 Offer II 046. 二叉树的右侧视图(dfs)
    private List<Integer> list = new ArrayList<>();
    private Set<Integer> set = new HashSet<>();//记录路径
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return list;
    }
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        //第一次到这个深度的一定是右子树
        if(!set.contains(depth)) {
            set.add(depth);
            list.add(root.val);
        }//若这个深度以前到达过，说明之前已经走过最右边了,就继续递归下去
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
    //5.剑指 Offer II 046. 二叉树的右侧视图(dfs)
    private List<Integer> list = new ArrayList<>();
    private int depthMain;
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return list;
    }
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }

        //第一次到这个深度的一定是右子树
        if(depthMain <= depth) {
            list.add(root.val);
            depthMain++;
        }
        //若这个深度以前到达过，说明之前已经走过最右边了,就继续递归下去
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
    //6.剑指 Offer II 044. 二叉树每层的最大值(dfs)
    private int depthMain;
    private List<Integer> list = new ArrayList<>();
    public List<Integer> largestValues(TreeNode root) {
        dfs(root, 0);
        return list;
    }
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        //走了同样的深度时，或是以前走过的深度，比较上次最大值
        if(depthMain >= depth) {
            //有两种可能：以前来过，或者是刚来
            if(list.size() >= depth + 1) {//以前来过
                if(root.val > list.get(depth)){
                    list.set(depth, root.val);
                }
            }else {//以前没来过
                list.add(root.val);
            }
            depthMain++;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
    //7.剑指 Offer II 044. 二叉树每层的最大值(忽然发现使用Math比较大小，效率还没if高...)
    private int depthMain;
    private List<Integer> list = new ArrayList<>();
    public List<Integer> largestValues(TreeNode root) {
        dfs(root, 0);
        return list;
    }
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        //走了同样的深度时，或是以前走过的深度，比较上次最大值
        if(depthMain >= depth) {
            //有两种可能：以前来过，或者是刚来
            if(list.size() >= depth + 1) {//以前来过
                list.set(depth, Math.max(list.get(depth), root.val));
            }else {//以前没来过
                list.add(root.val);
            }
            depthMain++;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
    //8.剑指 Offer II 056. 二叉搜索树中两个节点之和(中序+哈希表)
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        //利用二叉搜索树的性质，此问题可以下降为求升序序列两数之和
        if(root == null) {
            return false;
        }
        boolean left = findTarget(root.left, k);
        if(set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        boolean right = findTarget(root.right, k);
        return left || right;
    }
    //8.剑指 Offer II 056. 二叉搜索树中两个节点之和(可以不用二叉搜索树性质，其实就是两数之和那道题)
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        //其实也可以不用二叉搜索树性质...
        if(root == null) {
            return false;
        }
        if(set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
    //9.剑指 Offer II 053. 二叉搜索树中的中序后继(dfs设置标志位)
    private TreeNode target;
    private boolean flag = false;//判断是否遇到了前一个
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        fundOrder(root, p);
        return target;
    }
    private void fundOrder(TreeNode root, TreeNode p) {
        if(root == null) {
            return;
        }
        fundOrder(root.left, p);
        if(target == null && flag) {
            target = root;
            return;//后面就不用看了
        }
        if(target == null && root == p) {
            flag = true;
        }
        fundOrder(root.right, p);
    }
    //10.剑指 Offer II 054. 所有大于等于节点的值之和(dfs)
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        //先递归右边，先拿到的一定是右边最底下的结点
        dfs(root.right);
        sum += root.val;
        root.val = sum;
        dfs(root.left);
    }
    //10.剑指 Offer II 054. 所有大于等于节点的值之和(dfs优化)
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}
